partiels/partiel_MathsdisS3_S3_23 mars 2009.tex

   1 \documentclass[12pt,a4paper,french]{book}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage{dsfont}
  10 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  11 \usepackage[dvips]{graphics}
  12 \usepackage{epsfig}
  13 \usepackage{calc}
  14 \usepackage{tabls}
  15 \usepackage{slashbox}
  16 \usepackage{times}
  17 \usepackage{tabularx}
  18 \usepackage{textcomp}
  19
  20 \usepackage{pst-all}
  21
  22 \begin{document}
  23 \includegraphics{figures/LogoIUT.eps}
  24 \begin{center}
  25 \begin{Huge}
  26 Partiel de : Théorie des graphes\\
  27 Semestre 3 (23 mars 2009)\\
  28 \end{Huge}
  29 \end{center}
  30
  31 La calculatrice, ainsi qu'un quart de feuille A4, sont autorisés. Ce sujet contient 50 affirmations justes, et 50 fausses. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\
  32
  33 Q. 1. Les graphes hamiltoniens ont été définis au dix-neuvième siècle.\\
  34
  35 Q. 2. Une chaîne dans lequel tous les sommets sont différents s’appelle une chaîne simple.\\
  36
  37 Q. 3. Un graphe hamiltonien peut posséder un sommet de degré 2.\\
  38
  39 Q. 4. Soit $J$ la matrice d'adjacence d'un graphe non orienté. $J_{s,\varepsilon}$ vaut :
  40 \begin{itemize}
  41 \item 1 quand $s$ est une extrémité de l'arête $\varepsilon$ si celle-ci n'est pas une boucle,
  42 \item 2 quand $s$ est une extrémité de la boucle $\varepsilon$,
  43 \item 0 si $s$ n'est pas une extrémité de $\varepsilon$.
  44 \end{itemize}
  45
  46 Q. 5. Un graphe hamiltonien peut posséder un sommet de degré 3.L'assertion proposée est vraie ou fausse\\
  47
  48 Q. 6. La matrice d'adjacence d'un graphe non orienté est symétrique.\\
  49
  50 Q. 7. Un graphe est dit planaire si on arrive à le dessiner sans qu'aucune arête n'en coupe une autre.\\
  51
  52 Q. 8. L'inventeur des nombres complexes est aussi l'inventeur des graphes euleriens.\\
  53
  54 Q. 9. Un circuit eulérien est un circuit qui passe par tous les sommets du graphe.\\
  55
  56 Q. 10. Soit G un graphe connexe non eulérien. Il est toujours possible de rendre G eulérien en lui rajoutant un sommet et quelques arêtes.\\
  57
  58 Q. 11. S'il existe un sommet qui est connecté à tous les autres, alors le graphe considéré est connexe.\\
  59
  60 Q. 12. Le graphe suivant est biparti.
  61
  62 \begin{center}
  63 \includegraphics[scale=0.7]{figures/completK5.eps}
  64 \end{center}
  65
  66 Q. 13. Dans une matrice d'incidence, la somme des coefficients de la ligne $i$ est le degré du sommet $i$.\\
  67
  68 Q. 14.
  69 Le graphe $G$ :
  70
  71 \begin{center}
  72 \includegraphics[scale=0.75]{figures/graphe1bx.eps}
  73 \end{center}
  74
  75 a pour matrice d'incidence :
  76
  77 $$M = \left(
  78 \begin{array}{ccccc}
  79 0 ~~ 0 ~~ 1 ~~ 1 ~~ 1\\
  80 0 ~~ 0 ~~ 1 ~~ 0 ~~ 0\\
  81 1 ~~ 1 ~~ 0 ~~ 1 ~~ 1\\
  82 1 ~~ 0 ~~ 1 ~~ 0 ~~ 1\\
  83 1 ~~ 0 ~~ 1 ~~ 1 ~~ 0\\
  84 \end{array}
  85 \right)
  86 $$\\
  87
  88 Q. 15. Le graphe suivant est biparti.
  89
  90 \begin{center}
  91 \includegraphics[scale=0.7]{figures/arbre1.eps}
  92 \end{center}
  93
  94 Q. 16. $K_6$ est complet.\\
  95
  96 Q. 17. Le graphe suivant est complet
  97
  98 \begin{center}
  99 \includegraphics[scale=0.7]{figures/biparti.eps}
 100 \end{center}
 101
 102 Q. 18. Un graphe est dit planaire si toutes ses représentations sont telles qu'aucune arête n'en coupe une autre.\\
 103
 104 Q. 19. Une chaîne dont le départ et l'arrivée coïncident s'appelle un chemin.\\
 105
 106 Q. 20. Le graphe suivant est eulérien
 107
 108 \begin{center}
 109 \includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
 110 \end{center}
 111
 112 Q. 21. Le graphe ci-dessous est eulérien.
 113
 114 \begin{center}
 115 \includegraphics[scale=0.7]{figures/arbre1.eps}
 116 \end{center}
 117
 118 Q. 22. La question à l'origine du problème des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodécaèdre, de telle manière que le dernier sommet visité est aussi le premier.\\
 119
 120 Q. 23. Un arbre est un graphe non orienté.\\
 121
 122 Q. 24. Le graphe suivant est connexe.
 123
 124 \begin{center}
 125 \includegraphics[scale=0.7]{figures/completK5.eps}
 126 \end{center}
 127
 128 Q. 25. Un arbre est un graphe non orienté sans cycle.\\
 129
 130 Q. 26. Les expressions chaîne simple et chemin sont synonymes.\\
 131
 132 Q. 27. Le graphe suivant est eulerien.
 133
 134 \begin{center}
 135 \includegraphics[scale=0.7]{figures/completK5.eps}
 136 \end{center}
 137
 138 Q. 28. La matrice d'incidence est carrée.\\
 139
 140 Q. 29. $K_{m,n}$ possède $m+n$ arêtes.\\
 141
 142 Q. 30. Le degré du graphe suivant est 5.
 143
 144 \begin{center}
 145 \includegraphics[scale=0.7]{figures/completK5.eps}
 146 \end{center}
 147
 148 Q. 31. Le graphe suivant est planaire.
 149
 150 \begin{center}
 151 \includegraphics[scale=0.7]{figures/completK5.eps}
 152 \end{center}
 153
 154 Q. 32. Le degré du graphe suivant est 20.
 155
 156 \begin{center}
 157 \includegraphics[scale=0.7]{figures/completK5.eps}
 158 \end{center}
 159
 160 Q. 33. Un graphe est connexe s'il est possible, à partir de n'importe quel sommet, d'atteindre n'importe quel autre sommet du graphe.\\
 161
 162 Q. 34.
 163 Soit G un graphe. Le graphe G' est un graphe partiel de G, si on obtient G' en enlevant un ou plusieurs sommets au graphe G (avec les arêtes associées).\\
 164
 165 Q. 35. $K_n$ possède $n^2$ arêtes.\\
 166
 167 Q. 36. Le graphe suivant est biparti
 168
 169 \begin{center}
 170 \includegraphics[scale=0.7]{figures/grapheNonConnexe.eps}
 171 \end{center}
 172
 173 Q. 37.
 174 On considère des dominos dont les faces sont numérotées 1, 2, 3, 4 ou 5. Il est toujours possible d'arranger ces dominos de manière à former une boucle fermée.\\
 175
 176 Q. 38. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède ni arêtes parallèles, ni boucles, est de $n^{2}$.\\
 177
 178 Q. 39. Tous les $K_n$ sont hamiltoniens.\\
 179
 180 Q. 40. Il existe des graphes 3-réguliers simples à 6 sommets.\\
 181
 182 Q. 41.
 183 Représenter un graphe sous la forme d'une liste d'adjacence consiste à donner, pour chacun de ses sommets, la liste des sommets auxquels il est adjacent.\\
 184
 185 Q. 42.
 186 On appelle chaîne eulérienne une chaîne contenant une et une seule fois toutes les arêtes du graphe.\\
 187
 188 Q. 43.
 189 La question à l'origine du problème des graphes hamiltoniens est : comment passer une, et une seule fois, par chacun des sommets du dodécaèdre.\\
 190
 191 Q. 44. Si le graphe considéré n'a pas de boucle, alors la matrice d'adjacence associée a une diagonale nulle.\\
 192
 193 Q. 45. Il peut y avoir plusieurs circuits hamiltoniens dans un graphe hamiltonien.\\
 194
 195 Q. 46. Le graphe suivant est simple
 196
 197 \begin{center}
 198 \includegraphics[scale=0.7]{figures/grapheNonSimple.eps}
 199 \end{center}
 200
 201 Q. 47. Pour tout $n$, $K_n$ est complet.\\
 202
 203 Q. 48. Un graphe hamiltonien peut posséder un sommet de degré 3.\\
 204
 205 Q. 49. Un circuit eulérien est un circuit qui passe par toutes les arêtes du graphe.L'assertion proposée est vraie ou fausse\\
 206
 207 Q. 50. $K_n$ possède $\dfrac{n(n-1)}{2}$ sommets.\\
 208
 209 Q. 51. Le graphe suivant est hamiltonien.
 210
 211 \begin{center}
 212 \includegraphics[scale=0.7]{figures/completK5.eps}
 213 \end{center}
 214
 215 Q. 52.
 216 \begin{center}
 217 \includegraphics[scale=0.7]{figures/graphe9.eps}
 218 \end{center}
 219
 220 est un sous-graphe de
 221
 222 \begin{center}
 223 \includegraphics[scale=0.7]{figures/graphe7.eps}
 224 \end{center}
 225
 226 Q. 53. Hamilton est à l'origine du problème des graphes eulériens.\\
 227
 228 Q. 54. Un graphe hamiltonien ne possède pas de sommets de degré 1.L'assertion proposée est vraie ou fausse\\
 229
 230 Q. 55. Le corollaire de Dirac se déduit du théorème de Ore.L'assertion proposée est vraie ou fausse\\
 231
 232 Q. 56.
 233 Posséder un circuit eulérien est équivalent à n'avoir aucun sommet de degré impair.\\
 234
 235 Q. 57. Un circuit hamiltonien est un circuit qui passe par toutes les arêtes du graphe.\\
 236
 237 Q. 58. Il existe des graphes qui peuvent être hamiltoniens sans être eulériens.\\
 238
 239 Q. 59. $K_5$ est hamiltonien.\\
 240
 241 Q. 60.
 242 \begin{center}
 243 \includegraphics[scale=0.7]{figures/graphe9.eps}
 244 \end{center}
 245
 246 est un stable de
 247
 248 \begin{center}
 249 \includegraphics[scale=0.7]{figures/graphe7.eps}
 250 \end{center}
 251
 252 Q. 61. Dans le cas des graphes orientés, on parle de chemins, et dans le cas non orienté, de chaînes.\\
 253
 254 Q. 62. Dans le graphe suivant, le sommet 1 a pour degré 4.
 255
 256 \begin{center}
 257 \includegraphics[scale=0.7]{figures/completK5.eps}
 258 \end{center}
 259
 260 Q. 63. Le graphe suivant est connexe.
 261
 262 \begin{center}
 263 \includegraphics[scale=0.7]{figures/biparti.eps}
 264 \end{center}
 265
 266 Q. 64.
 267 Dans un circuit eulérien, le point de départ et d'arrivée coïncident.\\
 268
 269 Q. 65. Le théorème de Ore s'énonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.\\
 270
 271 Q. 66.
 272 Etre un graphe eulérien est équivalent à être connexe, sans sommet de degré impair.\\
 273
 274 Q. 67. Un circuit hamiltonien est un circuit qui passe par tous les sommets du graphe.L'assertion proposée est vraie ou fausse\\
 275
 276 Q. 68.
 277 \begin{center}
 278 \includegraphics[scale=0.7]{figures/graphe8.eps}
 279 \end{center}
 280
 281 est un sous-graphe partiel de
 282
 283 \begin{center}
 284 \includegraphics[scale=0.7]{figures/graphe7.eps}
 285 \end{center}
 286
 287 Q. 69.
 288 Posséder un circuit eulérien est équivalent à avoir 0 ou 2 sommets de degré impair.\\
 289
 290 Q. 70. Un graphe est dit complet s'il est en un seul tenant.\\
 291
 292 Q. 71.
 293 Etre un graphe eulérien est équivalent à n'avoir aucun sommet de degré impair.\\
 294
 295 Q. 72.
 296 Le graphe suivant est-il eulérien ?
 297
 298 \begin{center}
 299 \includegraphics[scale=0.7]{figures/eulerKonig}
 300 \end{center}
 301
 302 Q. 73. Il existe des graphes 3-réguliers simples à 8 sommets.\\
 303
 304 Q. 74. Le graphe suivant s'appelle $K_5$.
 305
 306 \begin{center}
 307 \includegraphics[scale=0.7]{figures/completK5.eps}
 308 \end{center}
 309
 310 Q. 75. Un graphe hamiltonien ne possède pas de sommets de degré 1.\\
 311
 312 Q. 76. $K_{m,n}$ désigne tout graphe ayant deux composantes connexes, la première avec $m$ sommets, et la seconde avec $n$ sommets.\\
 313
 314 Q. 77. Un graphe connexe est complet.\\
 315
 316 Q. 78. Le corollaire de Dirac sert à déterminer si un graphe est eulérien.L'assertion proposée est vraie ou fausse\\
 317
 318 Q. 79. Le degré d'un graphe est son nombre d'arêtes.\\
 319
 320 Q. 80. Un graphe dont tous les sommets ont le même degré est dit régulier.\\
 321
 322 Q. 81.
 323 Etre un graphe eulérien est équivalent à être connexe, avec 0 ou 2 sommets de degré impair.\\
 324
 325 Q. 82. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles, est de $n^{2}$.\\
 326
 327 Q. 83.
 328 Posséder une chaîne eulérienne est équivalent à être connexe, sans sommet de degré impair.\\
 329
 330 Q. 84.
 331 Le graphe $(S',A')$ est un sous-graphe du graphe $(S,A)$ si
 332 \begin{enumerate}
 333 \item $S' \subset S$,
 334 \item $A' \subset A$,
 335 \item $A'=\{(x,y)\mid (x,y) \in A \land x \in S' \land y \in S'\}$
 336 \end{enumerate}
 337
 338 Q. 85.
 339 On considère des dominos dont les faces sont numérotées de 1 à 7. Il est toujours possible d'arranger ces dominos de manière à former une boucle fermée.\\
 340
 341 Q. 86.
 342 Un graphe eulérien est un graphe possédant un circuit eulérien.\\
 343
 344 Q. 87. Le corollaire de Dirac s'énonce ainsi : Soit G = (V, E) un graphe simple d'ordre $n\geqslant 3$. Si pour toute paire \{x,y\} de sommets non adjacents, on a $d(x) + d(y) \geqslant n$, alors G est hamiltonien.L'assertion proposée est vraie ou fausse\\
 345
 346 Q. 88. Un graphe hamiltonien ne possède pas de sommets de degré 3.\\
 347
 348 Q. 89. Un graphe est dit simple, s’il ne contient pas de boucles et s’il n’y a pas plus d’une arête reliant deux mêmes sommets.\\
 349
 350 Q. 90. $K_2$ est hamiltonien.\\
 351
 352 Q. 91. Le graphe suivant est régulier.
 353
 354 \begin{center}
 355 \includegraphics[scale=0.7]{figures/arbre1.eps}
 356 \end{center}
 357
 358 Q. 92. Un graphe hamiltonien ne possède pas de sommets de degré 2.L'assertion proposée est vraie ou fausse\\
 359
 360 Q. 93.
 361 \begin{center}
 362 \includegraphics[scale=0.7]{figures/graphe8.eps}
 363 \end{center}
 364
 365 est un graphe partiel de
 366
 367 \begin{center}
 368 \includegraphics[scale=0.7]{figures/graphe7.eps}
 369 \end{center}
 370
 371 Q. 94. Le corollaire de Dirac se déduit du théorème de Ore.\\
 372
 373 Q. 95. Un graphe simple a un nombre impair de sommets de degré pair.\\
 374
 375 Q. 96. Le nombre maximal d'arêtes dans un graphe non orienté d'ordre $n$ qui ne possède pas d'arêtes parallèles, est de $\dfrac{n(n+1)}{2}$.\\
 376
 377 Q. 97. $K_n$ possède $n$ sommets.\\
 378
 379 Q. 98. Le lemme des poignées de mains dit que la somme des degrés des sommets est égale à deux fois le nombre d'arêtes.\\
 380
 381 Q. 99. $K_4$ est hamiltonien.\\
 382
 383 Q. 100.
 384 Le graphe $G$ suivant :
 385 \begin{center}
 386 \includegraphics[scale=0.7]{figures/graphe1b.eps}
 387 \end{center}
 388
 389 \noindent Possède pour liste d'adjacence :
 390
 391 1 : 3, 4, 5
 392
 393 2 : 3
 394
 395 3 : 1, 2, 5
 396
 397 4 : 1, 3, 5
 398
 399 5 : 1, 3, 4\\
 400
 401 \end{document}